'Weak Dependency Graph [60.0]' ------------------------------ Answer: YES(?,O(n^2)) Input Problem: innermost runtime-complexity with respect to Rules: { id(s(x)) -> s(id(x)) , id(0()) -> 0() , f(s(x)) -> f(id(x)) , f(0()) -> 0()} Details: We have computed the following set of weak (innermost) dependency pairs: { id^#(s(x)) -> c_0(id^#(x)) , id^#(0()) -> c_1() , f^#(s(x)) -> c_2(f^#(id(x))) , f^#(0()) -> c_3()} The usable rules are: { id(s(x)) -> s(id(x)) , id(0()) -> 0()} The estimated dependency graph contains the following edges: {id^#(s(x)) -> c_0(id^#(x))} ==> {id^#(0()) -> c_1()} {id^#(s(x)) -> c_0(id^#(x))} ==> {id^#(s(x)) -> c_0(id^#(x))} {f^#(s(x)) -> c_2(f^#(id(x)))} ==> {f^#(0()) -> c_3()} {f^#(s(x)) -> c_2(f^#(id(x)))} ==> {f^#(s(x)) -> c_2(f^#(id(x)))} We consider the following path(s): 1) { f^#(s(x)) -> c_2(f^#(id(x))) , f^#(0()) -> c_3()} The usable rules for this path are the following: { id(s(x)) -> s(id(x)) , id(0()) -> 0()} We have applied the subprocessor on the union of usable rules and weak (innermost) dependency pairs. 'Weight Gap Principle' ---------------------- Answer: YES(?,O(n^2)) Input Problem: innermost runtime-complexity with respect to Rules: { id(s(x)) -> s(id(x)) , id(0()) -> 0() , f^#(s(x)) -> c_2(f^#(id(x))) , f^#(0()) -> c_3()} Details: We apply the weight gap principle, strictly orienting the rules { id(0()) -> 0() , f^#(0()) -> c_3()} and weakly orienting the rules {} using the following strongly linear interpretation: Processor 'Matrix Interpretation' oriented the following rules strictly: { id(0()) -> 0() , f^#(0()) -> c_3()} Details: Interpretation Functions: 0() = [0] f(x1) = [0] x1 + [0] s(x1) = [1] x1 + [0] id(x1) = [1] x1 + [1] id^#(x1) = [0] x1 + [0] c_0(x1) = [0] x1 + [0] c_1() = [0] f^#(x1) = [1] x1 + [1] c_2(x1) = [1] x1 + [1] c_3() = [0] Finally we apply the subprocessor We apply the weight gap principle, strictly orienting the rules {f^#(s(x)) -> c_2(f^#(id(x)))} and weakly orienting the rules { id(0()) -> 0() , f^#(0()) -> c_3()} using the following strongly linear interpretation: Processor 'Matrix Interpretation' oriented the following rules strictly: {f^#(s(x)) -> c_2(f^#(id(x)))} Details: Interpretation Functions: 0() = [9] f(x1) = [0] x1 + [0] s(x1) = [1] x1 + [8] id(x1) = [1] x1 + [1] id^#(x1) = [0] x1 + [0] c_0(x1) = [0] x1 + [0] c_1() = [0] f^#(x1) = [1] x1 + [8] c_2(x1) = [1] x1 + [2] c_3() = [0] Finally we apply the subprocessor 'fastest of 'combine', 'Bounds with default enrichment', 'Bounds with default enrichment'' ------------------------------------------------------------------------------------------ Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0() , f^#(0()) -> c_3()} Details: The problem was solved by processor 'combine': 'combine' --------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0() , f^#(0()) -> c_3()} Details: 'sequentially if-then-else, sequentially' ----------------------------------------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0() , f^#(0()) -> c_3()} Details: 'if Check whether the TRS is strict trs contains single rule then fastest else fastest' --------------------------------------------------------------------------------------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0() , f^#(0()) -> c_3()} Details: a) We first check the conditional [Success]: We are considering a strict trs contains single rule TRS. b) We continue with the then-branch: The problem was solved by processor 'fastest of 'Matrix Interpretation', 'Matrix Interpretation', 'Matrix Interpretation'': 'fastest of 'Matrix Interpretation', 'Matrix Interpretation', 'Matrix Interpretation'' -------------------------------------------------------------------------------------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0() , f^#(0()) -> c_3()} Details: The problem was solved by processor 'Matrix Interpretation': 'Matrix Interpretation' ----------------------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0() , f^#(0()) -> c_3()} Details: Interpretation Functions: 0() = [0] [1] [1] f(x1) = [0 0 0] x1 + [0] [0 0 0] [0] [0 0 0] [0] s(x1) = [1 1 0] x1 + [0] [0 0 1] [1] [0 0 1] [1] id(x1) = [1 0 1] x1 + [0] [0 1 0] [0] [0 0 1] [0] id^#(x1) = [0 0 0] x1 + [0] [0 0 0] [0] [0 0 0] [0] c_0(x1) = [0 0 0] x1 + [0] [0 0 0] [0] [0 0 0] [0] c_1() = [0] [0] [0] f^#(x1) = [1 1 0] x1 + [1] [0 0 0] [1] [0 1 0] [1] c_2(x1) = [1 0 0] x1 + [1] [0 0 0] [1] [0 0 0] [1] c_3() = [0] [0] [0] 2) {f^#(s(x)) -> c_2(f^#(id(x)))} The usable rules for this path are the following: { id(s(x)) -> s(id(x)) , id(0()) -> 0()} We have applied the subprocessor on the union of usable rules and weak (innermost) dependency pairs. 'Weight Gap Principle' ---------------------- Answer: YES(?,O(n^2)) Input Problem: innermost runtime-complexity with respect to Rules: { id(s(x)) -> s(id(x)) , id(0()) -> 0() , f^#(s(x)) -> c_2(f^#(id(x)))} Details: We apply the weight gap principle, strictly orienting the rules {id(0()) -> 0()} and weakly orienting the rules {} using the following strongly linear interpretation: Processor 'Matrix Interpretation' oriented the following rules strictly: {id(0()) -> 0()} Details: Interpretation Functions: 0() = [0] f(x1) = [0] x1 + [0] s(x1) = [1] x1 + [0] id(x1) = [1] x1 + [1] id^#(x1) = [0] x1 + [0] c_0(x1) = [0] x1 + [0] c_1() = [0] f^#(x1) = [1] x1 + [1] c_2(x1) = [1] x1 + [1] c_3() = [0] Finally we apply the subprocessor We apply the weight gap principle, strictly orienting the rules {f^#(s(x)) -> c_2(f^#(id(x)))} and weakly orienting the rules {id(0()) -> 0()} using the following strongly linear interpretation: Processor 'Matrix Interpretation' oriented the following rules strictly: {f^#(s(x)) -> c_2(f^#(id(x)))} Details: Interpretation Functions: 0() = [1] f(x1) = [0] x1 + [0] s(x1) = [1] x1 + [8] id(x1) = [1] x1 + [1] id^#(x1) = [0] x1 + [0] c_0(x1) = [0] x1 + [0] c_1() = [0] f^#(x1) = [1] x1 + [8] c_2(x1) = [1] x1 + [2] c_3() = [0] Finally we apply the subprocessor 'fastest of 'combine', 'Bounds with default enrichment', 'Bounds with default enrichment'' ------------------------------------------------------------------------------------------ Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0()} Details: The problem was solved by processor 'combine': 'combine' --------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0()} Details: 'sequentially if-then-else, sequentially' ----------------------------------------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0()} Details: 'if Check whether the TRS is strict trs contains single rule then fastest else fastest' --------------------------------------------------------------------------------------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0()} Details: a) We first check the conditional [Success]: We are considering a strict trs contains single rule TRS. b) We continue with the then-branch: The problem was solved by processor 'fastest of 'Matrix Interpretation', 'Matrix Interpretation', 'Matrix Interpretation'': 'fastest of 'Matrix Interpretation', 'Matrix Interpretation', 'Matrix Interpretation'' -------------------------------------------------------------------------------------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0()} Details: The problem was solved by processor 'Matrix Interpretation': 'Matrix Interpretation' ----------------------- Answer: YES(?,O(n^2)) Input Problem: innermost relative runtime-complexity with respect to Strict Rules: {id(s(x)) -> s(id(x))} Weak Rules: { f^#(s(x)) -> c_2(f^#(id(x))) , id(0()) -> 0()} Details: Interpretation Functions: 0() = [1] [1] [0] f(x1) = [0 0 0] x1 + [0] [0 0 0] [0] [0 0 0] [0] s(x1) = [1 1 0] x1 + [0] [0 0 1] [1] [0 0 1] [1] id(x1) = [1 0 1] x1 + [0] [0 1 0] [0] [0 0 1] [0] id^#(x1) = [0 0 0] x1 + [0] [0 0 0] [0] [0 0 0] [0] c_0(x1) = [0 0 0] x1 + [0] [0 0 0] [0] [0 0 0] [0] c_1() = [0] [0] [0] f^#(x1) = [1 1 0] x1 + [1] [0 1 0] [0] [0 0 0] [1] c_2(x1) = [1 0 0] x1 + [0] [0 0 1] [0] [0 0 0] [1] c_3() = [0] [0] [0] 3) { id^#(s(x)) -> c_0(id^#(x)) , id^#(0()) -> c_1()} The usable rules for this path are empty. We have oriented the usable rules with the following strongly linear interpretation: Interpretation Functions: 0() = [0] f(x1) = [0] x1 + [0] s(x1) = [0] x1 + [0] id(x1) = [0] x1 + [0] id^#(x1) = [0] x1 + [0] c_0(x1) = [0] x1 + [0] c_1() = [0] f^#(x1) = [0] x1 + [0] c_2(x1) = [0] x1 + [0] c_3() = [0] We have applied the subprocessor on the resulting DP-problem: 'Weight Gap Principle' ---------------------- Answer: YES(?,O(n^1)) Input Problem: innermost DP runtime-complexity with respect to Strict Rules: {id^#(0()) -> c_1()} Weak Rules: {id^#(s(x)) -> c_0(id^#(x))} Details: We apply the weight gap principle, strictly orienting the rules {id^#(0()) -> c_1()} and weakly orienting the rules {id^#(s(x)) -> c_0(id^#(x))} using the following strongly linear interpretation: Processor 'Matrix Interpretation' oriented the following rules strictly: {id^#(0()) -> c_1()} Details: Interpretation Functions: 0() = [0] f(x1) = [0] x1 + [0] s(x1) = [1] x1 + [0] id(x1) = [0] x1 + [0] id^#(x1) = [1] x1 + [1] c_0(x1) = [1] x1 + [0] c_1() = [0] f^#(x1) = [0] x1 + [0] c_2(x1) = [0] x1 + [0] c_3() = [0] Finally we apply the subprocessor 'Empty TRS' ----------- Answer: YES(?,O(1)) Input Problem: innermost DP runtime-complexity with respect to Strict Rules: {} Weak Rules: { id^#(0()) -> c_1() , id^#(s(x)) -> c_0(id^#(x))} Details: The given problem does not contain any strict rules 4) {id^#(s(x)) -> c_0(id^#(x))} The usable rules for this path are empty. We have oriented the usable rules with the following strongly linear interpretation: Interpretation Functions: 0() = [0] f(x1) = [0] x1 + [0] s(x1) = [0] x1 + [0] id(x1) = [0] x1 + [0] id^#(x1) = [0] x1 + [0] c_0(x1) = [0] x1 + [0] c_1() = [0] f^#(x1) = [0] x1 + [0] c_2(x1) = [0] x1 + [0] c_3() = [0] We have applied the subprocessor on the resulting DP-problem: 'Weight Gap Principle' ---------------------- Answer: YES(?,O(n^1)) Input Problem: innermost DP runtime-complexity with respect to Strict Rules: {id^#(s(x)) -> c_0(id^#(x))} Weak Rules: {} Details: We apply the weight gap principle, strictly orienting the rules {id^#(s(x)) -> c_0(id^#(x))} and weakly orienting the rules {} using the following strongly linear interpretation: Processor 'Matrix Interpretation' oriented the following rules strictly: {id^#(s(x)) -> c_0(id^#(x))} Details: Interpretation Functions: 0() = [0] f(x1) = [0] x1 + [0] s(x1) = [1] x1 + [8] id(x1) = [0] x1 + [0] id^#(x1) = [1] x1 + [1] c_0(x1) = [1] x1 + [3] c_1() = [0] f^#(x1) = [0] x1 + [0] c_2(x1) = [0] x1 + [0] c_3() = [0] Finally we apply the subprocessor 'Empty TRS' ----------- Answer: YES(?,O(1)) Input Problem: innermost DP runtime-complexity with respect to Strict Rules: {} Weak Rules: {id^#(s(x)) -> c_0(id^#(x))} Details: The given problem does not contain any strict rules